package com.lw.leetcode.sort.c;

import com.lw.test.util.Utils;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * 786. 第 K 个最小的素数分数
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/17 16:18
 */
public class KthSmallestPrimeFraction {

    public static void main(String[] args) {
        KthSmallestPrimeFraction test = new KthSmallestPrimeFraction();

        // [2,5]
//        int[] arr = {1, 2, 3, 5};
//        int k = 3;

        // [1,7]
//        int[] arr = {1, 7};
//        int k = 1;

        int[] arr = Utils.getPrimeList(1000);
        int k = 500 * 999;
        System.out.println(k);
        System.out.println();

        int[] ints = test.kthSmallestPrimeFraction(arr, k);

        System.out.println(Arrays.toString(ints));
    }


    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> arr[(x >> 16)] * arr[y & 0XFFFF] - arr[(y >> 16)] * arr[x & 0XFFFF]);
        for (int j = 1; j < n; ++j) {
            pq.offer(j);
        }
        for (int i = 1; i < k; ++i) {
            int poll = pq.poll();
            int x = poll >> 16;
            int y = poll & 0XFFFF;
            if (x + 1 < y) {
                pq.offer(((x + 1) << 16) + y);
            }
        }
        int poll = pq.poll();
        return new int[]{arr[poll >> 16], arr[poll & 0XFFFF]};
    }

}
